package com.wenhai.leetcode.sort;

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Random;

/**
 *https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
 *
 * @author wenhai
 * @date   2021/3/1
 */
public class _剑指Offer40最小的k个数 {
    private static final Random RANDOM = new Random();
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        this.selectK(arr, 0, arr.length - 1, k - 1);
        return Arrays.copyOf(arr, k);
    }

    private int selectK(int[] arr, int l, int r, int k) {
        int p = partition(arr, l, r);
        if (p == k) {
            return arr[p];
        } else if (p > k) {
            return selectK(arr, l, p - 1, k);
        } else {
            return selectK(arr, p + 1, r, k);
        }
    }

    private int partition(int[] arr, int l, int r) {
        int p = l + RANDOM.nextInt(r - l + 1);
        swap(arr, l, p);
        int i = l + 1;
        int j = r;
        while (true){
            while (i <= j && arr[i] < arr[l]) {
                i++;
            }
            while (j >= i && arr[j] > arr[l]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            j--;
            i++;
        }
        swap(arr, l, j);
        return j;
    }
    private void swap(int[] nums, int srcPos, int destPos) {
        int temp = nums[srcPos];
        nums[srcPos] = nums[destPos];
        nums[destPos] = temp;
    }


    public int[] getLeastNumbers2(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < k; i++) {
            pq.add(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (!pq.isEmpty() && pq.peek() > arr[i]) {
                pq.remove();
                pq.add(arr[i]);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll();
        }
        return res;
    }



    public static void main(String[] args) {
        int[] arr = {0, 0, 1, 2, 4, 2, 2, 3, 1, 4};

    }
}
